package stack;

import java.util.Stack;

/**
 * @author cooper
 * @date 2019-07-09
 */
@SuppressWarnings("unchecked")
public class NewStack<T extends Comparable> {

    private Stack<T> dataStack = new Stack<>();
    private Stack<T> minStack = new Stack<>();

    /**
     * 入栈
     */
    public void push(T t) {
        dataStack.push(t);
        if (minStack.empty() || t.compareTo(minStack.peek()) <= 0) {
            minStack.push(t);
        } else {
            minStack.push(minStack.peek());
        }
    }

    /**
     * 出栈
     */
    public T pop() {
        minStack.pop();
        return dataStack.pop();
    }

    public T peek() {
        return dataStack.peek();
    }

    /**
     * 最小值
     */
    public T min() {
        return minStack.peek();
    }

    /**
     * 栈反转
     */
    public void reverse() {
        reverse(this.dataStack);
    }

    /**
     * 栈的反转 类似于汉诺塔的摆放
     */
    private void reverse(Stack<T> stack) {

        if (stack.empty()) {
            return;
        }
        T node1 = stack.pop();
        if (stack.empty()) {
            stack.push(node1);
            return;
        }
        reverse(stack);

        T node2 = stack.pop();
        reverse(stack);
        stack.push(node1);

        reverse(stack);
        stack.push(node2);
    }

    /**
     * 排序
     * 思路： 使用另一个栈
     */
    public void sort() {

        Stack<T> help = new Stack<>();

        Stack<T> dataStack = this.dataStack;

        while (!dataStack.empty()) {

            T data = dataStack.pop();
            if (help.empty()) {
                help.push(data);
                continue;
            }
            T t;
            while (!help.empty()) {
                t = help.peek();
                if (data.compareTo(t) < 0) {
                    dataStack.push(help.pop());
                } else {
                    break;
                }
            }
            help.push(data);
        }

        while (!help.empty()) {
            dataStack.push(help.pop());
        }
    }

    /**
     * 正序输出
     */
    @SuppressWarnings("unchecked")
    public void print() {
        Stack<T> clone = (Stack<T>) dataStack.clone();

        while (!clone.empty()) {
            T pop = clone.pop();
            System.out.println(pop);
        }
    }

    /**
     * 逆向打印
     */
    @SuppressWarnings("unchecked")
    public void reversePrint() {
        Stack<T> clone = (Stack<T>) dataStack.clone();

        reversePrint(clone);
    }

    /**
     * 用于递归
     */
    private void reversePrint(Stack<T> stack) {
        if (!stack.empty()) {
            T pop = stack.pop();
            reversePrint(stack);
            System.out.println(pop);
        }
    }

}
